// 题目描述
// 1220. 统计元音字母序列的数目
// 难度
// 困难
// 164
// 给你一个整数 n，请你帮忙统计一下我们可以按下述规则形成多少个长度为 n 的字符串：
// 字符串中的每个字符都应当是小写元音字母（'a', 'e', 'i', 'o', 'u'）
// 每个元音 'a' 后面都只能跟着 'e'
// 每个元音 'e' 后面只能跟着 'a' 或者是 'i'
// 每个元音 'i' 后面 不能 再跟着另一个 'i'
// 每个元音 'o' 后面只能跟着 'i' 或者是 'u'
// 每个元音 'u' 后面只能跟着 'a'
// 由于答案可能会很大，所以请你返回 模 10^9 + 7 之后的结果。
//   示例 1：
// 输入：n = 1
// 输出：5
// 解释：所有可能的字符串分别是："a", "e", "i" , "o" 和 "u"。
// 示例 2：
// 输入：n = 2
// 输出：10
// 解释：所有可能的字符串分别是："ae", "ea", "ei", "ia", "ie", "io", "iu", "oi", "ou" 和 "ua"。
// 示例 3：
// 输入：n = 5
// 输出：68
//   提示：
// 1 <= n <= 2 * 10^4
// 通过次数26,849提交次数44,218

/**
 * @param {number} n
 * @return {number}
 */
var countVowelPermutation = function (n) {
  const mod = 10 ** 9 + 7
  const dp = new Array(n).fill(0).map(item => new Array(5).fill(0))

  dp[0] = new Array(5).fill(1)

  for (let i = 1; i < n; i++) {
    // a
    {
      let p = 0
      p += dp[i - 1][1] % mod
      p += dp[i - 1][2] % mod
      p += dp[i - 1][4] % mod
      dp[i][0] = p % mod
    }
    // e
    {
      let p = 0
      p += dp[i - 1][0]
      p += dp[i - 1][2]
      dp[i][1] = p
    }
    // i
    {
      let p = 0
      p += dp[i - 1][1] % mod
      p += dp[i - 1][3] % mod
      dp[i][2] = p % mod
    }
    // o
    {
      let p = 0
      p += dp[i - 1][2] % mod
      dp[i][3] = p % mod
    }
    // u
    {
      let p = 0
      p += dp[i - 1][2] % mod
      p += dp[i - 1][3] % mod
      dp[i][4] = p % mod
    }
  }

  return dp[n - 1].reduce((cnt, cur) => (cnt + cur) % mod, 0) % mod
}

console.log(
  countVowelPermutation(
    5
  )
)






